package io.zhengsh.vvip.leetcode.dp;

public class Q42 {

    public static void main(String[] args) {

    }

    static class Solution {
        public int trap(int[] height) {
            // 数组涨肚
            int n = height.length;
            // 如果为 0 返回 0
            if (n == 0) {
                return 0;
            }

            // 左边最大值
            int[] leftMax = new int[n];
            leftMax[0] = height[0];
            for (int i = 1; i < n; ++i) {
                leftMax[i] = Math.max(leftMax[i - 1], height[i]);
            }

            // 右边最大值
            int[] rightMax = new int[n];
            rightMax[n - 1] = height[n - 1];
            for (int i = n - 2; i >= 0; --i) {
                rightMax[i] = Math.max(rightMax[i + 1], height[i]);
            }

            int ans = 0;
            for (int i = 0; i < n; ++i) {
                // 最低的柱子 - 底部柱子的高度，就是水的容量。
                ans += Math.min(leftMax[i], rightMax[i]) - height[i];
            }

            return ans;
        }
    }
}
